package com.lun.easy;

import java.util.LinkedList;

import com.lun.util.BinaryTree.TreeNode;

public class LeafSimilarTrees {
	
    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        
    	LinkedList<TreeNode> stack1 = new LinkedList<>(), //
    			stack2 = new LinkedList<>();
    	stack1.push(root1);
    	stack2.push(root2);
    	while(true) {
    		TreeNode leaf1 = getLeaf(stack1);
    		TreeNode leaf2 = getLeaf(stack2);
    		
    		if(leaf1 == null ^ leaf2 == null) {
    			return false;
    		}else if(leaf1 == null && leaf2 == null) {
    			return true;
    		}else {
    			if(leaf1.val != leaf2.val)
    				return false;
    		}
    	}
    }
    
    private TreeNode getLeaf(LinkedList<TreeNode> stack) {
    	
		while(!stack.isEmpty()) {    			
			TreeNode node = stack.pop();
			
			if(node.left == null && node.right == null)
				return node;
			
			if(node.right != null)
				stack.push(node.right);
			
			if(node.left != null)
				stack.push(node.left);
		}
    	
    	return null;
    }
    
}
